#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int kmp(char* s, int sLen, char* p, int pLen)
{
    char* next = (char*)malloc(pLen + 1);
    int i = 0, j = -1;
    int index = -1;

    next[i] = j;
    while (i < pLen)
    {
        while (j >= 0 && p[i] != p[j])
            j = next[j];
        j++;
        i++;
        next[i] = j;
    }

    printf("next: ");
    for (i = 0; i <= pLen; ++i)
    {
        printf("%d, ", next[i]);
    }
    printf("\n");

    i = 0;
    j = 0;
    while (i < sLen)
    {
        while (j >= 0 && s[i] != p[j])
            j = next[j];

        i++;
        j++;
        if (j == pLen)
        {
            index = i - j;
        }
    }

    free(next);
    return index;
}

int main(int argc, char** argv)
{
    char* s = "hello world";
    char* p = "wor";
    int index;
    if (argc != 3)
        return;
    s = argv[1];
    p = argv[2];

    index = kmp(s, strlen(s), p, strlen(p));
    printf ("find: %d\n", index);

    return 0;
}
